Selamat datang di Pelajaran 3 dari Artificial Intelligence Concepts (PolyU COMP5511). Pada sesi ini, kita beralih dari pencarian jalur agen tunggal ke Pencarian Adversarial, di mana agen beroperasi dalam lingkungan multi-agen yang kompetitif. Kita juga memperkenalkan Masalah Kepuasan Kendala (CSPs), sebuah paradigma di mana tujuannya adalah menemukan keadaan yang memenuhi serangkaian batasan tertentu, bukan mencari jalur.
Konsep Inti
- Pencarian Adversarial: Berfokus pada algoritma seperti Minimax dan Alpha-Beta Pruning untuk membuat keputusan rasional melawan lawan yang cerdas.
- Monte Carlo Tree Search (MCTS): Mengeksplorasi pengambilan keputusan probabilistik, menjadi tulang punggung bagi AI permainan modern seperti AlphaGo.
- Kepuasan Kendala: Memodelkan masalah menggunakan Variabel, Domain, dan Kendala, diselesaikan dengan Backtracking dan Pencarian Lokal.
Analisis Kompleksitas
Dalam pengaturan adversarial, kompleksitas ruang pencarian sering kali ditentukan oleh faktor percabangan permainan
Peringatan Pergeseran Paradigma
Berbeda dengan pencarian standar (misalnya, A* atau BFS) di mana lingkungan bersifat statis, Pencarian Adversarial mengasumsikan bahwa lingkungan (lawan) secara aktif mencoba meminimalkan keberhasilan Anda. Dalam CSP, urutan tindakan tidak terlalu penting dibandingkan validitas penetapan akhir.
Pseudocode Konseptual: Jenis Agen
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).